#include "stdafx.h"
#include "Status.h"

namespace compile
{
	// ------------------------------------- public --------------------------------------------
	Status::Status()
	{
		read_mark = ".";
	}

	Status::Status(Syntax* s, FollowWord* follow)
		:Status()
	{

		vector<Word>syntax = (*s).getWordVector();
		string enter = (*s).getEnter();
		action_table.initIndex(syntax);
		goto_table.initIndex(syntax);

		calculateStatusSet(syntax, enter);

		insertReducedData((*follow).getFollow());

	}



	Status::~Status()
	{
		read_mark.clear();
		status_set.clear();
		// action_table.~ActionTable();
		// goto_table.~GotoTable();

	}


	void Status::printStatusSet()
	{
		cout << "Status Set:" << endl;
		for (UNI i = 0; i < status_set.size(); ++i)
		{
			cout << i << ":" << endl;
			for (UNI j = 0; j < status_set.at(i).size(); ++j)
			{
				cout << status_set.at(i).at(j).first << "-->" << status_set.at(i).at(j).second << endl;
			}
			cout << "---------------------------------------------" << endl;
		}
	}

	void Status::print()
	{
		printStatusSet();
		cout << "---------------------------------------------" << endl;
		action_table.printTable();
		cout << "---------------------------------------------" << endl;
		goto_table.printTable();
		cout << "---------------------------------------------" << endl;
	}

	ActionTable Status::getActionTable() const
	{
		return action_table;
	}

	GotoTable Status::getGotoTable() const
	{
		return goto_table;
	}

	/**
	* 删除读取记号后返回开始状态集合
	* @return {vector<pair<string, string>>}
	*/
	vector<pair<string, string>> Status::getStartStatus() const
	{
		vector<pair<string, string>>result = status_set.at(0);
		for (UNI i = 0; i < result.size(); ++i)
		{
			result.at(i).second = deleteReadMark(result.at(i).second);
		}

		return result;
	}


	// ------------------------------------- public end ----------------------------------------------


	// ------------------------------------- private -------------------------------------------------


	/**
	* 计算状态集合
	* @param syntax {vector<Word>} 语法集合
	* @param enter {string} - 入口标记
	*/
	void Status::calculateStatusSet(vector<Word> syntax, string enter)
	{
		// 状态集合
		vector< pair<string, string> > status_pair_vector = initPairVector(syntax, enter);
		// 添加此状态进入status_set


		status_set.push_back(status_pair_vector);

		status_pair_vector.clear();

		// 直到不再添加状态
		for (UNI i = 0; i < status_set.size(); ++i)
		{

			// 没有处理空串归约，会出现问题
			vector< pair<string, string> > this_status = status_set.at(i);
			vector< pair<string, int> >next_sign_set = 
				getNextSignSet(this_status);

			string sign = next_sign_set.at(0).first;
			unsigned int start = 0;
			for (UNI j = 1; j <= next_sign_set.size(); ++j)
			{
				// 同一个
				if (j < next_sign_set.size() && 
					next_sign_set.at(j).first == sign)
				{
					continue;
				}
				// 不同
				else
				{
					// 获取新的集合
					// 查重
					// 更新sign和start
					status_pair_vector = getNewVector(this_status, 
						sign, 
						start, 
						j - 1, 
						&syntax);

					

					int pos_i = checkSet(status_pair_vector);

					if (status_pair_vector.size() != 0 &&  pos_i == -1)
					{
						status_set.push_back(status_pair_vector);

						// cout << i << ", " << sign << "->" << status_set.size() - 1 << endl;

						insertDataInTable(polyfillChar(i + 0x30), sign, status_set.size() - 1);
					}
					else if (pos_i != -1)
					{
						// cout << i << ", " << sign << "->" << pos_i << endl;

						insertDataInTable(polyfillChar(i + 0x30), sign, pos_i);
					}



					if (j != next_sign_set.size())
					{
						sign = next_sign_set.at(j).first;
						start = j;
					}

					

					status_pair_vector.clear();
					
				}
			}
		}
	}


	/**
	* 将归约数据插入表中
	* PS: 也许可以重构到ActionTable里去
	* @param follow {map<string, set<string>>} - follow集
	*/
	void Status::insertReducedData(map<string, set<string>> follow)
	{

		// vector<pair<string, string>>start_status = status_set.at(0);
		// 迭代状态集合
		for (UNI i = 0; i < status_set.size(); ++i)
		{
			vector<pair<string, string>> status = status_set.at(i);

			for (UNI j = 0; j < status.size(); ++j)
			{
				string content = status.at(j).second;
				string::size_type n = content.find(read_mark);

				// 读到末尾，可以归约
				if (n == content.length() - 1)
				{
					string key = status.at(j).first;
					// 进入符号
					if (key == "E_")
					{
						pair<string, string>index(polyfillChar(i + 0x30), "$");
						action_table.setTable(index, "acc");
					} 
					else
					{
						auto it = follow.find(key);

						// 找不到，follow集有问题，退出
						if (it == follow.end())
						{
							cout << "这个Follow集不清真!!!!" << endl;
							system("pause");
							exit(EXIT_FAILURE);
						}


						set<string>key_follow = it->second;

						unsigned int num_in_start = getIndexInStartStatus(key, content);
						// cout << num_in_start << endl;
						for (auto is = key_follow.begin(); is != key_follow.end(); ++is)
						{
							pair<string, string> index(changeInt(i), (*is));
							action_table.setTable(index, "r" + polyfillChar(num_in_start + 0x30));
						}
					}
					
				}
			}
		}
	}


	/**
	* 将转移数据插入表中
	* @param status_num {string} - 当前状态编号
	* @param status_sign {string} - 当前状态标记
	* @param change_num {int} - 转移向状态编号
	*/
	void Status::insertDataInTable(string status_num, string status_sign, int change_num)
	{
		pair<string, string> index(status_num, status_sign);
		
		// 终结符插入action_table
		if (ifEndSign(status_sign[0]))
		{
			string a = "s" + changeInt(change_num);
			action_table.setTable(index, a);
		}
		else
		{
			goto_table.setTable(index, changeInt(change_num));
		}
	}

	/**
	*/
	unsigned int Status::getIndexInStartStatus(string key, string content) const
	{
		pair<string, string> index(key, read_mark + deleteReadMark(content));
		vector <pair<string, string>> start_status = status_set.at(0);

		for (UNI i = 1; i < start_status.size(); ++i)
		{
			if (index == start_status.at(i))
			{
				return i;
			}
		}
		return 0;
	}


	/**
	* 检查该集合是否已存在
	* @param status_vector {vector<pair<string, string>>} - 被检测的状态集合
	* @return i {int} - 存在的位置
	*		-1 - 不存在
	*/
	int Status::checkSet(vector<pair<string, string>> status_vector)
	{
		for (UNI i = 0; i < status_set.size(); ++i)
		{
			auto checked_set = status_set.at(i);
			// 大小相等，有可能是同一集合
			if (checked_set.size() == status_vector.size())
			{
				UNI flag = 0;
				for (UNI j = 0; j < status_vector.size(); ++j)
				{

					for (UNI k = 0; k < checked_set.size(); ++k)
					{
						if (checked_set.at(k) == status_vector.at(j))
						{
							flag++;
							break;
						}
					}

				}

				if (flag == status_vector.size())
				{
					return i;
				}
			}
		}

		return -1;
	}

	/**
	* 获取新的状态
	* @param this_status {vector<pair<string, string>>} - 当前状态
	* @param sign {string} - 标记key
	* @param start {int} - 开始点
	* @param end {int} - 结束点
	* @param syntax {vector<Word>*} - 语法串集合
	* @return result {vector<pair<string, string>>} - 新集合
	*/
	vector<pair<string, string>> Status::getNewVector(
		vector<pair<string, string>> this_status,
		string sign, unsigned int start, unsigned int end, vector<Word>* syntax) const
	{
		vector<pair<string, string>> result;


		for (UNI i = start; i <= end; ++i)
		{
			pair<string, string>word_pair = this_status.at(i);
			word_pair.second = moveReadMark(word_pair.second);

			// 原本mark不在结尾
			if (word_pair.second.length() != 0)
			{
				result.push_back(word_pair);
			}
		}

		set<string> if_visited; // 加入访问过的key

		// 递归获取新的句法
		result = recureGetNewWord(result, syntax, &if_visited);


		return result;
	}


	/**
	* 获取文法
	* @param key {string} - 要添加的文法key
	* @param syntax {vector<Word>*} - 文法集合
	* @param if_visited {set<string>*} - 已访问过的元素集合
	* @return result {vector<pair<string, string>>} - 获取的结果
	*/
	vector<pair<string, string>> Status::getWord(string key, 
		vector<Word>* syntax, 
		set<string>* if_visited) const
	{
		vector < pair<string, string>> result;

		// 已访问过的key， 退出
		if ((*if_visited).find(key) == (*if_visited).end())
		{
			(*if_visited).insert(key);
		}
		else
		{
			return result;
		}

		// 迭代文法集合
		for (UNI i = 0; i < (*syntax).size(); ++i)
		{
			pair<string, string> word = (*syntax).at(i).getWord();

			if (word.first == key)
			{
				// 初始化走点
				word.second = initReadMark(word.second);
				result.push_back(word);
			}
		}

		// 递归获取非终结符的下一句
		result = recureGetNewWord(result, syntax, if_visited);

		return result;
	}

	/**
	* 迭代result，以便递归获取新文法
	* @param {vector<pair<string, string>>} result - 
	*							被搜索的状态集，确认走点符号后是否有非终结符
	* @param syntax {vector<Word>*} - 文法集合
	* @param if_visited {set<string>* if_visited} - 是否已访问过此key
	* @return {vector<pair<string, string>>} - 处理过的result
	*/
	vector<pair<string, string>> Status::recureGetNewWord(
		vector<pair<string, string>> result, 
		vector<Word>* syntax, 
		set<string>* if_visited) const
	{

		for (UNI i = 0; i < result.size(); ++i)
		{
			string content = result.at(i).second;
			string key = result.at(i).first;
			int position = content.find(read_mark);

			// read_mark 下一个为非终结符且其与key不相等
			if (content.length() - 1 > position &&
				!ifEndSign(content[position + 1]) &&
				content[position + 1] != key[0])
			{
				string new_key = polyfillChar(content[position + 1]);
				auto new_vector = getWord(new_key, syntax, if_visited);

				if (new_vector.size() > 0)
				{
					result = concatVector(result, new_vector);
				}

			}

		}


		return result;
	}


	/**
	* 走点
	* @param content {string} - 文法内容
	* @return result {string} "" - 木有点或者点到头了
	*		走点结果
	*/
	string Status::moveReadMark(string content) const
	{
		string::size_type n = content.find(read_mark);
		string result;
		if (n == string::npos || n == content.length() - 1)
		{
			result = "";
		}
		else
		{
			result = content.substr(0, n) + 
				content.substr(n + 1, 1) + 
				read_mark + 
				content.substr(n + 2);
		}
		return result;
	}

	/**
	* 获取即将读取的下一个字符
	* @param {vector<pair<string, string>>} this_status - 当前状态集合
	* @return result {vector<pair<string, int>>} - 下一个被读取的字符集合
	*/
	vector<pair<string, int>> Status::getNextSignSet(vector<pair<string, string>> this_status) const
	{
		vector<pair<string, int>>result;

		for (UNI i = 0; i < this_status.size(); ++i)
		{
			string key = this_status.at(i).first;
			string content = this_status.at(i).second;
			auto read_mark_position = content.find(read_mark);
			if (read_mark_position != string::npos)
			{
				// 下一个字符
				result.push_back(
					pair<string, int>(content.substr(read_mark_position + 1, 1), i));
			}
		}

		return result;
	}

	/**
	* 初始化句法
	* @param {string} content - 推导出的句子
	* @return {string} - read_mark + content
	*/
	string Status::initReadMark(string content) const
	{
		return read_mark + content;
	}


	/**
	* 初始化首状态
	* @param syntax {vector<Word>} - 文法集合
	* @return result {vector<pair<string, string>>} - 初始化的vector
	*/
	vector<pair<string, string>> Status::initPairVector(vector<Word> syntax, string enter) const
	{
		vector <pair<string, string>> result;

		// 开始
		result.push_back(pair<string, string>(enter + polyfillChar('_'), read_mark + enter));
		for (UNI i = 0; i < syntax.size(); ++i)
		{
			string key = syntax.at(i).getKey();
			string content = syntax.at(i).getContent();

			// 初始化首状态，添加read_mark
			pair<string, string> word_pair(key, this->read_mark + content);
			result.push_back(word_pair);
		}

		return result;
	}

	/**
	* 连接两个向量
	* @param result {vector<pair<string, string>>} - 要返回的向量
	* @param new_vector {vector<pair <string, string>>} - 连接在后的向量
	* @return result {vector<pair<string, string>>}
	*/
	vector<pair<string, string>> Status::concatVector(
		vector<pair<string, string>> result,
		vector<pair<string, string>> new_vector)
	{
		for (UNI i = 0; i < new_vector.size(); ++i)
		{
			result.push_back(new_vector.at(i));
		}

		return result;
	}


	/**
	* 将字符转为字符串
	* @param {char} new_char - 被转的字符
	* @return 目标字符串
	*/
	string Status::polyfillChar(char new_char)
	{
		char a[2];
		a[0] = new_char;
		a[1] = '\0';
		return a;
	}

	/**
	* 判断是否为终结符
	* @param {char} sign - 被判断的字符
	* @return true - 是终结符
	*		false - 不是终结符
	*/
	bool Status::ifEndSign(char sign)
	{
		if (!(sign >= 'A' && sign <= 'Z'))
		{
			return true;
		}
		return false;
	}


	string Status::changeInt(int change_num)
	{
		string result;
		vector<char> num_char_vector;

		while (change_num != 0)
		{
			num_char_vector.push_back((change_num % 10) + 0x30);
			change_num = change_num / 10;
		}
		
		result.resize(num_char_vector.size());
		for (UNI i = 0; i < num_char_vector.size(); ++i)
		{
			result[i] = num_char_vector.at(num_char_vector.size() - 1 - i);
		}

		return result;
	}

	/**
	* 删除读取记号
	* @param content {string} - 文法内容
	* @return {string} - 删除read_mark后的文法
	*/
	string Status::deleteReadMark(string content) const
	{
		auto it = content.find(read_mark);
		if (it == string::npos)
		{
			return content;
		}
		else if (it == content.length() - 1)
		{
			return content.substr(0, content.length() - 1);
		}
		return content.substr(0, it) + content.substr(it + 1);
	}


	// --------------------------------- private end ---------------------------------------------
}